package com.arron.algorithm.leetcodetop100.动态规划;

import java.util.Arrays;

/**
 *  打家劫舍一系列套路题解
 *   https://leetcode.cn/problems/house-robber-ii/solutions/67465/tong-yong-si-lu-tuan-mie-da-jia-jie-she-wen-ti-by-/
 */
public class 打家劫舍 {

    int[] dp;

    public int rob(int[] nums) {

        if (nums.length == 1){
            return nums[0];
        }

        if (nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
         dp = new int[nums.length];
        Arrays.fill(dp,-1);
        return rob(nums,nums.length-1);
    }

    public int rob(int[] nums,int start){

        if (start<0){
            return 0;
        }
        if (dp[start] != -1) {
            return dp[start];
        }
        dp[start] =Math.max(rob(nums,start-2)+nums[start] , rob(nums,start-1));
        return dp[start];

    }

    public int rob_plus(int[] nums){


        int[] dp = new int[nums.length+2];

        for (int i = nums.length-1; i >= 0 ; i--) {


            dp[i]  = Math.max(dp[i+2]+nums[i],dp[i+1]);

        }

        return dp[0];
    }


    public static void main(String[] args) {

        打家劫舍 rob = new 打家劫舍();
        int[] nums = {2,7,9,3,1};
        rob.rob(nums);

    }

}
